package 笔试.a空白.c;

import MyUtils.MHUtils;
import org.junit.Test;

public class Main {
    public int minDistance(String w1, String w2) {
        char[] s1 = w1.toCharArray();
        char[] s2 = w2.toCharArray();
        int n1 = s1.length, n2 = s2.length;

        int[][] dp = new int[n1 + 1][n2 + 1];

        // 表格出边界
        // |A
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = i;
        }
        // ——
        for (int j = 0; j < dp[0].length; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                // 特 不是base哦 （注意 gird原始数据-1 因为dp我扩了）
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i - 1][j - 1];
                    continue;
                }


                dp[i][j] = MHUtils.min3(
                        dp[i][j - 1] + 1, // * dpij = 不要少加当前
                        dp[i - 1][j] + 1,
                        dp[i - 1][j - 1] + 1
                );
            }
        }
        return dp[n1][n2];// 最后一个计算的 -> 必须是 minLen
    }


    @Test
    public void test() {
        System.out.println("RES:" + minDistance("XAABZ", "ABCDEABCD"));
    }
}
/*
ABCDEABCD
XAABZ
 */
